/**********************************************************************
 * file:  sr_router.c
 * date:  Mon Feb 18 12:50:42 PST 2002
 * Contact: casado@stanford.edu
 *
 * Description:
 *
 * This file contains all the functions that interact directly
 * with the routing table, as well as the main entry function
 * for routing.
 *
 **********************************************************************/

#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>

#include <sys/time.h>

#include "sr_if.h"
#include "sr_rt.h"
#include "sr_router.h"
#include "sr_protocol.h"
#include "sr_arpcache.h"
#include "sr_utils.h"

#include "Parser.c"

#define DEBUG_1


/* Note: sr_send_packet will send a buffer out on the wire immediately.
 * It's defined in sr_vns_comm.c with the following format:

int sr_send_packet(struct sr_instance* sr,
                         uint8_t* buf,
                         unsigned int len,
                         const char* iface)

 * The passed in buffer should include everything that needs to go on the wire,
 * including the ethernet headers, so don't call this until you have all the
 * necessary information (e.g., you know the MAC address of the destination. */


/*---------------------------------------------------------------------

 * Function: sr_init(void)
 * Scope:  Global
 *
 * Initialize the routing subsystem
 *
 *---------------------------------------------------------------------*/
/* You probably don't need to change this. */
void sr_init(struct sr_instance* sr)
{
    /* REQUIRES */
    assert(sr);

    /* Initialize cache and cache cleanup thread */
    sr_arpcache_init(&(sr->cache));

    pthread_attr_init(&(sr->attr));
    pthread_attr_setdetachstate(&(sr->attr), PTHREAD_CREATE_JOINABLE);
    pthread_attr_setscope(&(sr->attr), PTHREAD_SCOPE_SYSTEM);
    pthread_attr_setscope(&(sr->attr), PTHREAD_SCOPE_SYSTEM);
    pthread_t thread;

    pthread_create(&thread, &(sr->attr), sr_arpcache_timeout, sr);

} /* -- sr_init -- */

/* Function: ether_to_me:
 * returns 1 if this local router should process this ethernet packet
 * (if it is to this address or to broadcast)
 * You shouldn't need to change this.
 */
int ether_to_me(unsigned char* my_address, unsigned char* addr_s){
    unsigned char * addr = (unsigned char *)addr_s;
#ifdef DEBUG_1
    Debug("\nMy Address:  %x:%x:%x:%x:%x:%x    Dest:   %x:%x:%x:%x:%x:%x\n",
	  my_address[0], my_address[1], my_address[2], my_address[3],
	  my_address[4], my_address[5], addr[0], addr[1], addr[2], 
	  addr[3], addr[4], addr[5] );
#endif
    return ((memcmp(my_address,addr_s,ETHER_ADDR_LEN)==0) ||
            ((addr[0] & addr[1] & addr[2] & addr[3] & addr[4] & addr[5]) == 0xff));
}

/*---------------------------------------------------------------------
 * Function: sr_handlepacket(uint8_t* p,char* interface)
 * Scope:  Global
 *
 * This function is called each time the router receives a packet on the
 * interface.  The packet buffer, the packet length and the receiving
 * interface are passed in as parameters. The packet is complete with
 * ethernet headers.
 *
 * Note: Both the packet buffer and the character's memory are handled
 * by sr_vns_comm.c that means do NOT delete either.  Make a copy of the
 * packet instead if you intend to keep it around beyond the scope of
 * the function call.
 *
 *---------------------------------------------------------------------*/
void sr_handlepacket(struct sr_instance* sr,
        uint8_t * packet/* lent */,
        unsigned int len,
        char* interface/* lent */)
{
    struct sr_if *incoming_interface;
    uint8_t *quad;

    /* REQUIRES */
    assert(sr);
    assert(packet);
    assert(interface);

    /* incoming_interface has a field named 'addr', which tells you the MAC
     * address of the interface that received the packet.  You can use that,
     * along with ether_to_me to determine whether or not this packet is
     * relevant to your router. */
    incoming_interface = sr_get_interface(sr, interface);
    quad = (uint8_t *) &incoming_interface->ip;

    printf("*** -> Received packet of length %d on interface %s (%d.%d.%d.%d.)\n",
        len, interface, quad[0], quad[1], quad[2], quad[3]);

    // verify that the ethernet frame has a valid length
    if ( len < 42 || len > ETH_MAX_LEN ) {
      // Frame is invalid length
      Debug("\nDropping packet that is too short");
      return;
    }
    
    // drop the packet if it does not apply to this interface
    ethernetHeader hdr;
    memcpy( hdr.data, packet, 14 );
    parseEthernet( &hdr );
    if ( ! ether_to_me(incoming_interface->addr, packet) ) {
      Debug("\nReceived packet is not to me. Dropping.");
      // Ethernet not destined for me
      return;
    }
    if ( hdr.arp_flag ) {
#ifdef DEBUG_1
      Debug("\nReceived packet is an ARP Packet.");
#endif
      handle_arp(sr, &packet[14], len - 14, interface);
    }
    else if (hdr.ip_flag) {
#ifdef DEBUG_1
      Debug("\nReceived packet is an IP Packet.");
#endif
      handle_ip (sr, &packet[14], len - 14, interface);
    }
    else {
      Debug("\nReceived Packet is not IP or Arp - Dropping");
      // Not IP or Arp
      return;
    }
    return;
    
}

/* This packet is either an arp request and we are responsible for replying
 * with our ethernet address or this is an arp reply hopefully to a request we
 * have sent out, in which case we add the entry to our cache. */
int handle_arp(struct sr_instance *sr, uint8_t *packet, unsigned int len, char *interface)
{
    struct sr_arp_hdr * arp_header;
    struct sr_if * intf;
    struct sr_arpreq * req;
    uint32_t this_interface_ip;
    arp_header = (struct sr_arp_hdr *) packet;
    intf = sr_get_interface(sr, interface);
#ifdef DEBUG_1
    Debug("\nInterface intf:  %x:%x:%x:%x:%x:%x",
	  intf->addr[0], intf->addr[1], intf->addr[2], 
	  intf->addr[3], intf->addr[4], intf->addr[5] );
#endif
    /* ARP request or reply? */
    switch (ntohs(arp_header->ar_op))
    {
    case arp_op_request:
      Debug("\nReceived Arp Request.");
      this_interface_ip = intf->ip;
            
      if (! ip_to_me( sr, arp_header->ar_tip ) ) {
#ifdef DEBUG_1	
	Debug("\nArp request not destined to me");
#endif
	return 1;
      }
      uint8_t reply[ sizeof(sr_ethernet_hdr_t) + sizeof(sr_arp_hdr_t) ];
      struct sr_arp_hdr * reply_arp = 
	(struct sr_arp_hdr*) &reply[sizeof(sr_ethernet_hdr_t)];
      struct sr_ethernet_hdr * reply_ether = 
	(struct sr_ethernet_hdr*) reply;
      // Set the fields in the ethernet header
      memcpy( reply_ether->ether_dhost, arp_header->ar_sha, ETHER_ADDR_LEN );
      memcpy( reply_ether->ether_shost, intf->addr, ETHER_ADDR_LEN );
      enum sr_ethertype type = ethertype_arp;
      reply_ether->ether_type = htons(type);
      
      // Set the fields in the arp header
      // Header should be the same except for the operation and a swap of the 
      // source / dest ethernet and IP addresses
      memcpy( reply_arp, arp_header, sizeof(sr_arp_hdr_t) );
      enum sr_arp_opcode opcode = arp_op_reply;
      reply_arp->ar_op = htons( opcode );
      memcpy( reply_arp->ar_sha, intf->addr , ETHER_ADDR_LEN );
      memcpy( reply_arp->ar_tha, arp_header->ar_sha, ETHER_ADDR_LEN );
      reply_arp->ar_sip = this_interface_ip; //arp_header->ar_tip;
      reply_arp->ar_tip = arp_header->ar_sip;
#ifdef DEBUG_1
      Debug("\nSource is: %x:%x:%x:%x:%x:%x\n",
	    reply_arp->ar_sha[0], reply_arp->ar_sha[1], reply_arp->ar_sha[2],
	    reply_arp->ar_sha[3], reply_arp->ar_sha[4], reply_arp->ar_sha[5]);
#endif
      sr_send_packet( sr, reply, sizeof(sr_ethernet_hdr_t) + sizeof(sr_arp_hdr_t), intf->name );
      
      
      break;
    case arp_op_reply:
      Debug("\nReceived Arp Reply.");
      // Store the arp reply in the router's arp cache
      req = sr_arpcache_insert(&sr->cache, arp_header->ar_sha, arp_header->ar_sip);
      // req is a sr_arpreq* that can now be sent
      if ( ! req ) {
	// Nothing pending on this arp
	break;
      }
      struct sr_packet * cur = req->packets;
      while ( cur ) {
	memcpy( cur->buf, arp_header->ar_sha, ETHER_ADDR_LEN );
	// Now, packet is ready to be sent
	sr_send_packet( sr, cur->buf, cur->len, cur->iface );
	cur = cur->next;
      }
      sr_arpreq_destroy( &sr->cache, req); 
      break;
    default:
      Debug("\ndropping unhandleable ARP packet");
    }
    return 0;
}

int handle_ip(struct sr_instance *sr, uint8_t * packet,unsigned int len,char * interface)
{
    struct sr_ip_hdr * hdr = (struct sr_ip_hdr *)packet;
    
    // Compute the checksum
    short theirCheckSum = hdr->ip_sum;
    short myCheckSum = checksum_ip( hdr );
    if ( myCheckSum != theirCheckSum ) {
      Debug("\nChecksums Incorrect:  Mine: %d   Theirs: %d",
	    myCheckSum, theirCheckSum);
    }
#ifdef DEBUG_1
    Debug("\nChecksum for IP header correct. Both %d", myCheckSum);
    Debug("\nHeader IP without ntohl: %d   With: %d", hdr->ip_dst, ntohl(hdr->ip_dst) );
#endif
    if ( ip_to_me( sr, hdr->ip_dst ) ) {
      Debug("\nIP Packet is destined for me.");
      if ( hdr->ip_p == 1 ) {
	Debug("\nProtocol is ICMP");
	sr_icmp_hdr_t * icmp = (sr_icmp_hdr_t*) (packet + IPV4_HEADER_LEN);
	if ( icmp->icmp_type == ICMP_TYPE_ECHO_REQUEST ) {
	  // Ping request
	  Debug("\nRequest is for ping");
	  icmp_handle_packet(sr, packet, len);
	}
	else {
	  Debug("\nRequest is not for ping: %d", icmp->icmp_type);
	  icmp_send( sr, hdr->ip_src, sr_get_interface(sr, interface)->ip, 
		     packet, ICMP_DATA_SIZE,
		     ICMP_TYPE_DEST_UNREACH, ICMP_CODE_PROTO_UNREACH, 0, 0 );
	}
      }
      else {
	Debug("\nRequest is not ICMP");
	icmp_send( sr, hdr->ip_src, sr_get_interface(sr, interface)->ip, 
		   packet, ICMP_DATA_SIZE,
		   ICMP_TYPE_DEST_UNREACH, ICMP_CODE_PORT_UNREACH, 0, 0 );
      }
      return 1;
    }
    
    Debug("\nPacket not my IP address.");

    // Packet is not destined for me
    hdr->ip_ttl -= 1;
    if ( ! hdr->ip_ttl ) {
      // Packet expired
      // TODO - does checksum need to be recomputed here before sending out?
      icmp_send( sr, hdr->ip_src, 0, packet, len, ICMP_TYPE_TIME_EXCEEDED,
		 ICMP_CODE_TTL_EXPIRED, 0, 0 );
      return 1;
    }
    
    // Update the IP checksum
    checksum_ip( hdr );

    if(!router_send_ethernet_frame(sr,hdr->ip_dst,htons(ethertype_ip),
				   packet,len))
      {
        Debug("Couldn't find a route to forward IP packet\n");
        icmp_send(sr,hdr->ip_src,0,packet,len,ICMP_TYPE_DEST_UNREACH, 0 , 0, 0); // Code 0 = network unreachable
        return 6;
      }
    return 0;
    
}

/* Compute a checksum for an IP header.  You shouldn't need to change this. */
uint16_t checksum_ip(struct sr_ip_hdr * hdr ) {
    hdr->ip_sum = 0;
    hdr->ip_sum = checksum( (uint16_t*)hdr, IPV4_HEADER_LEN );
    return hdr->ip_sum;
}

/* Compute a checksum for an arbitrary buffer, given a size.  You shouldn't
 * need to change this. */
uint16_t checksum(uint16_t* buf, unsigned len) {
    uint16_t answer;
    uint32_t sum;

    /* add all 16 bit pairs into the total */
    answer = sum = 0;
    while( len > 1 ) {
        sum += *buf++;
        len -= 2;
    }

    /* take care of the last lone uint8_t, if present */
    if( len == 1 ) {
        *(unsigned char *)(&answer) = *(unsigned char *)buf;
        sum += answer;
    }

    /* fold any carries back into the lower 16 bits */
    sum = (sum >> 16) + (sum & 0xFFFF);    /* add hi 16 to low 16 */
    sum += (sum >> 16);                    /* add carry           */
    answer = ~sum;                         /* truncate to 16 bits */

    return answer;
}

/* Allocates memory for an ICMP message, fills in the header fields, and calls
 * one of two appropriate functions to encapsulate it in a packet and send it
 * on its way. */
void icmp_send(struct sr_instance * sr,
	       uint32_t dst,
	       uint32_t src,
	       uint8_t* ip_packet, /* or just the data to send back */
	       unsigned len,
	       uint8_t type,
	       uint8_t code,
	       uint16_t id,
	       uint16_t seq) {
  
#ifdef DEBUG_1
  Debug("\nGot %d bytes to send back in ICMP", len);
  int i;
  for (i = 0; i < 32; i++) {
    if ( ! (i % 8) ) {
      Debug("\n");
    }
    Debug(" 0x%2x ", ip_packet[i]);
  }
#endif

  uint8_t buf[len + 
	      (sizeof(struct sr_icmp_t3_hdr) > sizeof(struct sr_icmp_hdr) ? 
	       sizeof(struct sr_icmp_t3_hdr) : sizeof(struct sr_icmp_hdr))];
  struct sr_icmp_t3_hdr * icmp3 = (struct sr_icmp_t3_hdr*) buf;
  struct sr_icmp_hdr * icmp = (struct sr_icmp_hdr*) buf;
  if ( type == 3 ) {
    icmp3->icmp_type = type;
    icmp3->icmp_code = code;
    icmp3->next_mtu = 0; // No fragmentation
    
    memcpy( icmp3->data, ip_packet, ICMP_DATA_SIZE );
    
    icmp3->icmp_sum = checksum_icmp( (sr_icmp_hdr_t*) icmp3, sizeof(sr_icmp_t3_hdr_t));
  }
  else {
    icmp->icmp_type = type;
    icmp->icmp_code = code;
    icmp->icmp_id = (id);
    icmp->icmp_seq = (seq);
    memcpy( icmp+1, ip_packet, len );
    icmp->icmp_sum = checksum_icmp( icmp, len + sizeof(sr_icmp_hdr_t) );
  
  }
  
  if (src) {
    /* If we we're given the source, call ip_send_packet_from, which lets
     * us specify the src address. */
  
    if ( type == 3 ) {
      ip_send_packet_from( sr, dst, src, IP_PROTO_ICMP, buf, sizeof(sr_icmp_t3_hdr_t));
      }
      else {
	ip_send_packet_from( sr, dst, src, IP_PROTO_ICMP, buf, len + sizeof(sr_icmp_hdr_t));
      }    
  
  } else {
    /* If we weren't given the source, it means this router *is* the
     * source. Call ip_send_packet, which will figure out which of the
     * router's interfaces to sent it out, and use that interface's IP
     * address as the source. */
      if ( type == 3 ) {
	ip_send_packet( sr, dst, IP_PROTO_ICMP, buf, sizeof(sr_icmp_t3_hdr_t));
      }
      else {
 	ip_send_packet( sr, dst, IP_PROTO_ICMP, buf, len + sizeof(sr_icmp_hdr_t));
     }

  }
}

/* Given a destination, it looks up the interface to forward it out.
 * You shouldn't need to change this. */
struct sr_if * router_lookup_interface_via_ip(struct sr_instance * sr, uint32_t dst)
{
    /* Use rtable_find_route to find route, then look up sr_if based on route
     * interface's name. */
    struct sr_rt * route = rtable_find_route(sr,dst);
    return sr_get_interface(sr,route->interface);

}

/* Sends an IP packet from this router.  Given the destination of the packet,
 * it looks up which of its own IP addresses it should use as the source
 * address and then calls ip_send_packet_from() to craft the packet.
 * Returns 0 on success, non-zero on failure.
 * You shouldn't need to change this. */
int ip_send_packet(struct sr_instance * router,
        uint32_t dst,
        uint8_t proto_id,
        uint8_t* payload,
        unsigned len ) {
    struct sr_if * intf;
    uint32_t found_src;
    uint8_t * quad = (uint8_t*)&dst;
    int result = 0;

    /* lookup the src address we'll send from to get to dst */
    // outgoing interface
    intf = router_lookup_interface_via_ip( router, dst );
    if(intf) {
        // outgoing interface's IP
        found_src = intf->ip;
        result = ip_send_packet_from(router, dst, found_src, proto_id, payload, len);
    }

    /* couldn't route to dst */
    Debug( "Error: unable to find route in ip_send_packet for %u.%u.%u.%u\n",quad[0],quad[1],quad[2],quad[3] );

    return result;
}


/* Walks the list of local interfaces and returns True if the destination
 * matches one of them (i.e., it's destined for this router). You shouldn't
 * need to change this. */
int ip_to_me(struct sr_instance * sr, uint32_t dst)
{
    struct sr_if* if_walker = sr->if_list;
    while(if_walker)
    {
#ifdef DEBUG_1
      Debug("\nChecking IP's:  Mine %d   Dest %d", if_walker->ip, dst);
#endif
      if (if_walker->ip ==dst) {
	return 1;
      }
      if_walker = if_walker->next;
    }
    return 0;
}

/* Sends back an ICMP echo (ping) reply upon receiving a ping request.
 * You shouldn't need to change this function. */
void icmp_handle_packet(struct sr_instance * router,
        uint8_t* ip_packet,
        unsigned len ) {
    struct sr_ip_hdr *  hdr_ip;
    sr_icmp_hdr_t* hdr;
    unsigned headers_len;
    unsigned icmp_packet_len;
    uint16_t old_sum;

    hdr = (sr_icmp_hdr_t*)(ip_packet + IPV4_HEADER_LEN);
    icmp_packet_len = len - IPV4_HEADER_LEN;

    /* We assume only ICMP echo messages are the only thing we'll receive. */
    if( hdr->icmp_type != ICMP_TYPE_ECHO_REQUEST ) {
        Debug( "%s only Echo Request and Reply is handled (received type %u)",
                "ICMP packet dropped:",
                hdr->icmp_type );
        return;
    }

    /*  Do a checkum, and throw it out if the checksum fails. */
    old_sum = hdr->icmp_sum;
    if(old_sum != checksum_icmp(hdr, icmp_packet_len) ) {
        Debug( "\n%s checksum 0x%x is incorrect:: should be 0x%x\n",
                "ICMP packet dropped:",
                old_sum,
                hdr->icmp_sum );
        return;
    }

    /* Determine how much data ame with the request */
    headers_len = IPV4_HEADER_LEN + ICMP_HEADER_LEN;

    /* Send the echo reply back to sender from us (swapped dst/src fields) */
    hdr_ip = (struct sr_ip_hdr*)ip_packet;
    icmp_send( router,
            hdr_ip->ip_src, hdr_ip->ip_dst,
            ip_packet+headers_len, len - headers_len,
            ICMP_TYPE_ECHO_REPLY, 0, hdr->icmp_id, hdr->icmp_seq);
}

/* Compute a checksum for ICMP.  You shouldn't need to change this. */
uint16_t checksum_icmp(sr_icmp_hdr_t* icmp_hdr, unsigned total_len) {
    icmp_hdr->icmp_sum = 0;
    icmp_hdr->icmp_sum = checksum( (uint16_t*)icmp_hdr, total_len );
    return icmp_hdr->icmp_sum;
}

/* Allocates memory for a packet, fills in the header fields, and calls
 * router_send_ethernet_frame() to get the packet on its way. */
int ip_send_packet_from( struct sr_instance* router,
        uint32_t dst,
        uint32_t src,
        uint8_t proto_id,
        uint8_t* buf,
        unsigned len ) {

    int ret = 0;
    uint8_t packet[len + IPV4_HEADER_LEN];
    sr_ip_hdr_t *  ip = (sr_ip_hdr_t*) &packet;
    ip->ip_hl = 5;
    ip->ip_v = 4;
    ip->ip_tos = 0;
    ip->ip_len = htons(IPV4_HEADER_LEN + len);
    ip->ip_id  = 0; 
    ip->ip_off = 1 << 6 ;
    ip->ip_ttl = 100;
    ip->ip_p = proto_id;
    ip->ip_src = src;
    ip->ip_dst = dst; 
    memcpy( ip+1, buf, len );
    checksum_ip( ip );

    ret = router_send_ethernet_frame( router, dst, htons(0x0800), 
				      packet, len + IPV4_HEADER_LEN );
    
    return ret;
}

static int bitsInCommon( uint32_t first, uint32_t second ) {
  
  int toRet = 0;
  int idx = 31;
  while ( idx >= 0 ) {
    if ((first & ( 1 << idx) ) == (second & (1 << idx)) ) {
      toRet += 1;
      idx -= 1;
    }
    else {
      return toRet;
    }
  }
  return toRet;

}

static int bitsInPrefix( uint32_t prefix ) {
  int toRet = 0;
  int i = 0;
  for (i = 0; i < 32; i++) {
    if ( prefix & ( 1 << i ) ) {
      toRet += 1;
    }
  }
  return toRet;
  
}



/* Given a routing table and destination IP address, this function should
 * return the interface out which you'd send to reach that destination. */
struct sr_rt * rtable_find_route(struct sr_instance * sr, uint32_t dst_ip)
{
    
  struct sr_rt * toRet = NULL;
  int longestMatch = 0;
  struct sr_rt * iter = sr->routing_table;
  
  while ( iter ) {
    int match = bitsInCommon( dst_ip, iter->dest.s_addr );
    if ( match >= bitsInPrefix(iter->mask.s_addr) ) {
      if ( match > longestMatch ) {
	longestMatch = match;
	toRet = iter;
      }
    }
    iter = iter->next;
  }
  
  fprintf(stderr, "\nRTable Find Route: Route Through: %s.",
	  ( toRet ? toRet->interface : "NULL"));
  fflush(stderr);

  return toRet;

}

/* Given a packet and destination, this finds the interface to use and calls
 * router_queue_ethernet_frame to queue it for sending.  You shouldn't need
 * to change this. */
int router_send_ethernet_frame( struct sr_instance * router,
        uint32_t dst_ip,
        uint16_t type,
        uint8_t* payload,
        unsigned len ) {
    struct sr_rt * rti;
    struct sr_if * intf;
    /* lookup which route to use */
    rti = rtable_find_route( router, dst_ip );
    if( !rti ) {
        Debug("no route for this IP\n");
        return 0; /* don't have a route for this IP */
    }
    intf = sr_get_interface(router,rti->interface);
    Debug("\nSending frame to address ");
    print_addr_ip_int( dst_ip );
    Debug(" out on interface %s", intf->name);
    router_queue_ethernet_frame(router, rti, intf, type, payload, len );
    
    return 1;
}

/* Craft an ethernet frame (buf) by encapsulating the given payload.
 * Do a check to see if we have all the relevant information (namely, the
 * destination MAC address) to send the packet.  If so, send it.  If not
 * queue it until we can resolve the destination MAC via ARP. */
int router_queue_ethernet_frame(struct sr_instance * sr,
        struct sr_rt * rti,
        struct sr_if * intf,
        uint16_t type,
        uint8_t* payload,
        unsigned payload_len ) {

    struct sr_arpentry *arp_entry;
    struct sr_arpreq * req;
    int len = payload_len + 14;
    uint8_t buf[len + 14];
    
    
    struct sr_ethernet_hdr * hdr = (struct sr_ethernet_hdr*) buf;
    memcpy( hdr->ether_shost, intf->addr, ETHER_ADDR_LEN );
    hdr->ether_type = type; //htons( type );
#ifdef DEBUG_1
    Debug("\nEthernet Type is: %d   (htons is %d)", type, htons(type));
#endif
    memcpy( hdr+1, payload, payload_len );

    arp_entry = sr_arpcache_lookup(&sr->cache, rti->gw.s_addr);
    if(arp_entry)
    {
      Debug("\nFound arp entry for ethernet frame.");
      memcpy( hdr->ether_dhost, arp_entry->mac, ETHER_ADDR_LEN );
      sr_send_packet( sr, buf, len, intf->name );

    } else{
      Debug("\nQueueing request for arp for ethernet frame.");
        /* If we don't have an entry in our ARP cache for this destination,
         * we can't send the packet yet, since we don't know who to address it
         * to at the link layer (ethernet).  In this case, we add it to a queue
         * of packets that are waiting for the MAC address to be resolved, and
         * then call handle_arpreq, which will generate and send an ARP
         * request, if necessary. */
        req = sr_arpcache_queuereq(&sr->cache, rti->gw.s_addr, buf, len, intf->name);
        handle_arpreq(sr,req);
    }

    free(arp_entry);
    return 0;
}


/* This function is called:
 * 1) By router_queue_ethernet_frame() above when it goes to send a frame and discovers
 * that it does not already know the MAC address of the destination.
 * 2) Every ~1 second by a thread that sweeps through every entry in the cache.
 *
 * struct sr_arpreq is defined in sr_arpcache.h as:
 *
 * struct sr_arpreq {
    uint32_t ip;
    time_t sent;                   Last time this ARP request was sent. You
                                   should update this. If the ARP request was
                                   never sent, will be 0.
    uint32_t times_sent;           Number of times this request was sent. You
                                   should update this.
    struct sr_packet *packets;     List of pkts waiting on this req to finish
    struct sr_arpreq *next;
 */
int handle_arpreq(struct sr_instance * sr,struct sr_arpreq * req)
{
    /* You shouldn't need to worry about the locking of this structure.  In case you're
     * digging around and looking at this lock, it's initialized as a recursive pthread
     * mutex, so don't panic if it looks like it's being locked multiple times by the
     * same thread, that's ok as long as it does an equal number of unlocks. */
    pthread_mutex_lock(&(sr->cache.lock));

    struct timeval tv;
    gettimeofday( &tv, NULL );
    int current = tv.tv_sec;

    if ( (current - req->sent) > 0 ) {
      if (req->times_sent >= 5) {
	struct sr_packet * iter = req->packets;
	while ( iter ) {
	  // Send host unreachable icmp
	  struct sr_ip_hdr * hdr = (struct sr_ip_hdr*) &iter->buf[14]; // pointer to raw ethernet frame
	  icmp_send( sr, hdr->ip_src, sr_get_interface(sr, iter->iface)->ip, 
		     (uint8_t *) hdr, ICMP_DATA_SIZE, 
		     ICMP_TYPE_DEST_UNREACH, ICMP_CODE_HOST_UNREACH, 0, 0 );
	  iter = iter->next;
	}
	sr_arpreq_destroy(&sr->cache, req);
      }
      else {
	
	// generate an arp and send it out
	uint8_t arp[14 + sizeof(sr_arp_hdr_t)];
	uint8_t * src = sr_get_interface(sr, req->packets->iface)->addr;	
	uint8_t dest[6] = {0xff, 0xff, 0xff, 0xff, 0xff, 0xff};
	uint8_t type[2] = {0x08, 0x06};
	struct sr_ip_hdr * ipH = (struct sr_ip_hdr *) &req->packets->buf[14];
	uint32_t ipSrc = sr_get_interface(sr, req->packets->iface)->ip;	
	uint32_t ipDest = ipH->ip_dst;
	memcpy(arp, dest, 6);
	memcpy(&arp[6], src, 6);
	memcpy(&arp[12], type, 2);
	struct sr_arp_hdr * arpH = (struct sr_arp_hdr*) &arp[14];
	arpH->ar_hrd = htons( 1 );
	arpH->ar_pro = htons( 0x0800 );
	arpH->ar_hln = 6;
	arpH->ar_pln = 4;
	arpH->ar_op = htons( 1 );
	memcpy( arpH->ar_sha, src, ETHER_ADDR_LEN );
	arpH->ar_sip = ipSrc; 
	memset( arpH->ar_tha, 0, 6 );
	arpH->ar_tip = ipDest;
	req->times_sent ++;
	req->sent = current;

	sr_send_packet( sr, arp, 14 + sizeof(sr_arp_hdr_t), req->packets->iface );
      }


    }
    pthread_mutex_unlock(&(sr->cache.lock));
    return 0;
}
